﻿/**
  @(#)$Id: AL_TreeHuffmanList.h 82 2013-10-17 08:39:02Z xiaoting $
  @brief	Tree (tree) that contains n (n> 0) nodes of a finite set, where:
	(1) Each element is called node (node);
	(2) there is a particular node is called the root node or root (root).
	(3) In addition to the remaining data elements other than the root node is divided into m (m ≥ 0) disjoint set of T1, T2, ...... 
	Tm-1, wherein each set of Ti (1 <= i <= m ) itself is a tree, the original tree is called a subtree (subtree).
  
  
  Trees can also be defined as: the tree is a root node and several sub-tree consisting of stars. And a tree is a set defined on the 
  set consisting of a relationship. Elements in the collection known as a tree of nodes, the defined relationship is called 
  parent-child relationship. Parent-child relationship between the nodes of the tree establishes a hierarchy. In this there is a 
  hierarchy node has a special status, this node is called the root of the tree, otherwise known as root.

  We can give form to the tree recursively defined as follows:
	Single node is a tree, the roots is the node itself.
	Let T1, T2, .., Tk is a tree, the root node are respectively n1, n2, .., nk. With a new node n as n1, n2, .., nk's father, then 
	get a new tree node n is the new root of the tree. We call n1, n2, .., nk is a group of siblings, they are sub-node n junction. 
	We also said that n1, n2, .., nk is the sub-tree node n.

	Empty tree is also called the empty tree. Air no node in the tree.

 The related concepts of tree 
  1. Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
  2. Height or depth of the tree: the maximum level of nodes in the tree;
  3. Forests: the m (m> = 0) disjoint trees set of trees called forest;

  The related concepts of tree node 
  1.degree		degree node: A node of the subtree containing the number is called the node degree;
  2.leaf			leaf nodes or terminal nodes: degree 0 are called leaf nodes;
  3.branch		non-terminal node or branch node: node degree is not 0;
  4.parent		parent node or the parent node: If a node contains a child node, this node is called its child node's parent;
  5.child			child node or child node: A node subtree containing the root node is called the node's children;
  6.slibing		sibling nodes: nodes with the same parent node is called mutual sibling;
  7.ancestor		ancestor node: from the root to the node through all the nodes on the branch;
  8.descendant	descendant nodes: a node in the subtree rooted at any node is called the node's descendants.
  
  ////////////////////////////////Huffman tree//////////////////////////////////////////
  Given n weights as n-leaf nodes, construct a binary tree, if the weighted path length to a minimum, said this is the optimal 
  binary tree, also known as Huffman (Huffman tree).

  ////////////////////////////////Binary Tree//////////////////////////////////////////
  In computer science, a binary tree is that each node has at most two sub-trees ordered tree. Usually the root of the subtree is 
  called "left subtree" (left subtree) and the "right subtree" (right subtree). Binary tree is often used as a binary search tree 
  and binary heap or a binary sort tree. Binary tree each node has at most two sub-tree (does not exist a degree greater than two 
  nodes), left and right sub-tree binary tree of the points, the order can not be reversed. Binary i-th layer of at most 2 power 
  nodes i -1; binary tree of depth k at most 2 ^ (k) -1 nodes; for any binary tree T, if it is the terminal nodes (i.e. leaf nodes) 
  is, the nodes of degree 2 is, then = + 1.

  ////////////////////////////////Complete Binary Tree//////////////////////////////////////////
  If set binary height of h, the h layer in addition, the other layers (1 ~ h-1) has reached the maximum number of nodes, right to 
  left, the h-layer node number of consecutive missing, this is a complete binary tree .

  ////////////////////////////////Full Binary Tree//////////////////////////////////////////
  A binary tree of height h is 2 ^ h-1 element is called a full binary tree.

  ////////////////////////////////Chain storage structure//////////////////////////////////////////
  The computer using a set of arbitrary linear table storage unit stores data elements (which may be a continuous plurality of memory 
  cells, it can be discontinuous).

  It does not require the logic elements of adjacent physical location is adjacent to and therefore it is not sequential storage 
  structure has a weakness, but also lost the sequence table can be accessed randomly advantages.

  Chain store structural features:
  1, compared with sequential storage density storage structure (each node consists of data fields and pointers domains, so the same 
  space is full, then assume full order of more than chain stores).
  2, the logic is not required on the adjacent node is physically adjacent.
  3, insert, delete and flexible (not the mobile node, change the node as long as the pointer).
  4, find the node when stored sequentially slower than the chain stores.
  5, each node is a pointer to the data fields and domains.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-17 16:39:02 +0800 (周四, 17 十月 2013) $
  @Revision $Revision: 82 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeHuffmanList.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeHuffmanList.h 82 2013-10-17 08:39:02Z xiaoting $
 */

#ifndef CXX_AL_TREEHUFFMANLIST_H
#define CXX_AL_TREEHUFFMANLIST_H

#ifndef CXX_AL_LISTSINGLE_H
#include "AL_ListSingle.h"
#endif

#ifndef CXX_AL_QUEUELIST_H
#include "AL_QueueList.h"
#endif

#ifndef CXX_AL_TREENODEBINLIST_H
#include "AL_TreeNodeBinList.h"
#endif

#ifndef CXX_AL_STACKLIST_H
#include "AL_StackList.h"
#endif

#ifndef CXX_AL_QUEUEPRIORITYLIST_H
#include "AL_QueuePriorityList.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_TreeHuffmanList
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_TreeHuffmanList
{
	static const DWORD TREEHUFFMANLIST_HEIGHTINVALID			= 0xffffffff;
public:
	/**
	* Construction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	AL_TreeHuffmanList();

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention 
	*/
	~AL_TreeHuffmanList();

	/**
	* IsEmpty
	*
	* @param VOID
	* @return BOOL
	* @note the tree has data?
	* @attention
	*/
	BOOL IsEmpty() const;
	
	/**
	* GetRootNode
	*
	* @param
	* @return	const AL_TreeNodeBinList<T>*
	* @note Get the root data
	* @attention 
	*/
	const AL_TreeNodeBinList<T>* GetRootNode() const;

	/**
	* GetDegree
	*
	* @param
	* @return	DWORD
	* @note Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
	* @attention 
	*/
	DWORD GetDegree() const;


	/**
	* GetHeight
	*
	* @param	
	* @return	DWORD
	* @note Height or depth of the tree: the maximum level of nodes in the tree;
	* @attention 
	*/
	DWORD GetHeight() const;

	/**
	* GetNodesNum
	*
	* @param
	* @return	DWORD
	* @note get the notes number of the tree 
	* @attention 
	*/
	DWORD GetNodesNum() const;

	/**
	* Clear
	*
	* @param
	* @return	
	* @note 
	* @attention 
	*/
	VOID Clear();

	/**
	* PreOrderTraversal
	*
	* @param	AL_ListSingle<T>& listOrder <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @return	BOOL
	* @note Pre-order traversal
	* @attention 
	*/
	BOOL PreOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;

	/**
	* InOrderTraversal
	*
	* @param	AL_ListSingle<T>& listOrder <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @return	BOOL
	* @note In-order traversal
	* @attention 
	*/
	BOOL InOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;

	/**
	* PostOrderTraversal
	*
	* @param	AL_ListSingle<T>& listOrder <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @return	BOOL
	* @note Post-order traversal
	* @attention 
	*/
	BOOL PostOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;

	/**
	* LevelOrderTraversal
	*
	* @param	AL_ListSingle<T>& listOrder <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @return	BOOL
	* @note Level-order traversal
	* @attention 
	*/
	BOOL LevelOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;

	/**
	* GetSiblingAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<T>& listSibling <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetSiblingAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<T>& listSibling, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;

	/**
	* GetAncestorAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<T>& listAncestor <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetAncestorAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<T>& listAncestor, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;

	/**
	* GetDescendantAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<T>& listDescendant <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetDescendantAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<T>& listDescendant, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;

	/**
	* InsertRoot
	*
	* @param	const T& tData <IN> 
	* @param	DWORD dwWeight <IN> 
	* @return	BOOL
	* @note
	* @attention
	*/
	BOOL InsertRoot(const T& tData, DWORD dwWeight);

	/**
	* InsertLeftAtNode
	*
	* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	const T& tData <IN> 
	* @param	DWORD dwWeight <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (left)
	* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertLeftAtNode(AL_TreeNodeBinList<T>* pCurTreeNode, const T& tData, DWORD dwWeight);

	/**
	* InsertRightAtNode
	*
	* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	const T& tData <IN> 
	* @param	DWORD dwWeight <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (right)
	* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertRightAtNode(AL_TreeNodeBinList<T>* pCurTreeNode, const T& tData, DWORD dwWeight);

	/**
	* Remove
	*
	* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @return	BOOL
	* @note 
	* @attention  the current tree node must be in the tree, remove current node and include it's descendant note
	*/
	BOOL Remove(AL_TreeNodeBinList<T>* pCurTreeNode);

	/**
	* GetChildNodeLeftAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @return	const AL_TreeNodeBinList<T>*
	* @note get the current tree node (pCurTreeNode)'s child node at the position (left)
	* @attention the current tree node must be in the tree
	*/
	const AL_TreeNodeBinList<T>* GetChildNodeLeftAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode) const;

	/**
	* GetChildNodeRightAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @return	const AL_TreeNodeBinList<T>*
	* @note get the current tree node (pCurTreeNode)'s child node at the position (right)
	* @attention the current tree node must be in the tree
	*/
	const AL_TreeNodeBinList<T>*  GetChildNodeRightAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode) const;

	/**
	* IsCompleteTreeBin
	*
	* @param
	* @return	BOOL
	* @note Is Complete Binary Tree
	* @attention If set binary height of h, the h layer in addition, the other layers (1 ~ h-1) has reached the maximum number of 
	             nodes, right to left, the h-layer node number of consecutive missing, this is a complete binary tree .
	*/
	BOOL  IsCompleteTreeBin() const;

	/**
	* IsFullTreeBin
	*
	* @param
	* @return	BOOL
	* @note Is Full Binary Tree
	* @attention A binary tree of height h is 2 ^ h-1 element is called a full binary tree.
	*/
	BOOL  IsFullTreeBin() const;

	/**
	* ConvertToHuffman
	*
	* @param
	* @return	BOOL
	* @note Convert current binary tree to Huffman tree (binary tree)
			Suppose there are n weights, then construct a Huffman tree with n leaf nodes. n-weights are set to w1, w2, ..., wn, the Huffman tree structure rules:
				(1) The w1, w2, ..., wn as a forest tree with n (each tree has only one node);
				(2) in the forest root weights elect two smallest tree merge as a new tree in the left and right sub-tree, and the new root of the tree weight of its left and right sub-tree root node weights sum;
				(3) Delete selected from the forest two trees and new trees added to the forest;
				(4) Repeat (2), (3) step until only one tree in the forest until the tree is that obtained from Huffman tree.
	* @attention
	*/
	BOOL  ConvertToHuffman();

protected:
private:
	
	/**
	* InsertAtNode
	*
	* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	DWORD dwIndex <IN>
	* @param	const T& tData <IN> 
	* @param	DWORD dwWeight <IN> 
	* @return	BOOL
	* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (dwIndex)
	* @attention if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
	*/
	BOOL InsertAtNode(AL_TreeNodeBinList<T>* pCurTreeNode, DWORD dwIndex, const T& tData, DWORD dwWeight);

	/**
	* PreOrderTraversal
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note Pre-order traversal
	* @attention
	*/
	BOOL PreOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const;

	/**
	* InOrderTraversal
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note In-order traversal
	* @attention
	*/
	BOOL InOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const;

	/**
	* PostOrderTraversal
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note Post-order traversal
	* @attention
	*/
	BOOL PostOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const;

	/**
	* LevelOrderTraversal
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note Level-order traversal
	* @attention 
	*/
	BOOL LevelOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const;

	/**
	* PreOrderTraversalRecursion
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note Pre-order traversal
	* @attention Recursion Traversal
	*/
	BOOL PreOrderTraversalRecursion(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const;

	/**
	* InOrderTraversalRecursion
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note In-order traversal
	* @attention Recursion Traversal
	*/
	BOOL InOrderTraversalRecursion(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const;

	/**
	* PostOrderTraversalRecursion
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
	* @return	BOOL
	* @note Post-order traversal
	* @attention Recursion Traversal
	*/
	BOOL PostOrderTraversalRecursion(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const;

	/**
	* GetSiblingAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling <OUT>
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetSiblingAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling) const;

	/**
	* GetAncestorAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetAncestorAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor) const;

	/**
	* GetDescendantAtNode
	*
	* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention the current tree node must be in the tree
	*/
	BOOL GetDescendantAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant) const;

	/**
	* RecalcDegreeHeight
	*
	* @param	
	* @return	BOOL
	* @note recalculate Degree Height
	* @attention 
	*/
	BOOL RecalcDegreeHeight();

		/**
	* GetListDataFormListNode
	*
	* @param	
	* @param	const AL_ListSingle<AL_TreeNodeBinList<T>*>& listNode <IN>
	* @param	AL_ListSingle<T>& listData <OUT>
	* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
	* @note
	* @attention 
	*/
	BOOL GetListDataFormListNode(const AL_ListSingle<AL_TreeNodeBinList<T>*>& listNode, AL_ListSingle<T>& listData, AL_ListSingle<DWORD>& listWeight = AL_ListSingle<DWORD>()) const;
	
	/**
	*Copy Construct
	*
	* @param	const AL_TreeHuffmanList<T>& cAL_TreeHuffmanList
	* @return
	*/
	AL_TreeHuffmanList(const AL_TreeHuffmanList<T>& cAL_TreeHuffmanList);

	/**
	*Assignment
	*
	* @param	const AL_TreeHuffmanList<T>& cAL_TreeHuffmanList
	* @return	AL_TreeHuffmanList<T>&
	*/
	AL_TreeHuffmanList<T>& operator = (const AL_TreeHuffmanList<T>& cAL_TreeHuffmanList);

public:
protected:
private:
	DWORD								m_dwDegree;
	DWORD								m_dwHeight;
	DWORD								m_dwNumNodes;
	AL_TreeNodeBinList<T>*				m_pRootNode;
};

///////////////////////////////////////////////////////////////////////////
//			AL_TreeHuffmanList
///////////////////////////////////////////////////////////////////////////

/**
* Construction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_TreeHuffmanList<T>::AL_TreeHuffmanList():
m_dwDegree(0x00),
m_dwHeight(TREEHUFFMANLIST_HEIGHTINVALID),
m_dwNumNodes(0x00),
m_pRootNode(NULL)
{

}

/**
* Destruction
*
* @param
* @return
* @note
* @attention 
*/
template<typename T> 
AL_TreeHuffmanList<T>::~AL_TreeHuffmanList()
{
	Clear();
}

/**
* IsEmpty
*
* @param VOID
* @return BOOL
* @note the tree has data?
* @attention
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::IsEmpty() const
{
	return (0x00 == m_dwNumNodes) ? TRUE:FALSE;
}

/**
* GetRootNode
*
* @param
* @return	const AL_TreeNodeBinList<T>*
* @note Get the root data
* @attention 
*/
template<typename T> const AL_TreeNodeBinList<T>* 
AL_TreeHuffmanList<T>::GetRootNode() const
{
	return m_pRootNode;
}

/**
* GetDegree
*
* @param
* @return	DWORD
* @note Degree of tree: a tree, the maximum degree of the node of the tree is called degree;
* @attention 
*/
template<typename T> DWORD 
AL_TreeHuffmanList<T>::GetDegree() const
{
	return m_dwDegree;
}


/**
* GetHeight
*
* @param	
* @return	DWORD
* @note Height or depth of the tree: the maximum level of nodes in the tree;
* @attention 
*/
template<typename T> DWORD 
AL_TreeHuffmanList<T>::GetHeight() const
{
	return m_dwHeight;
}

/**
* GetNodesNum
*
* @param
* @return	DWORD
* @note get the notes number of the tree 
* @attention 
*/
template<typename T> DWORD 
AL_TreeHuffmanList<T>::GetNodesNum() const
{
	return m_dwNumNodes;
}

/**
* Clear
*
* @param
* @return	
* @note 
* @attention 
*/
template<typename T> VOID 
AL_TreeHuffmanList<T>::Clear()
{
	m_dwDegree = 0x00;
	m_dwHeight = TREEHUFFMANLIST_HEIGHTINVALID;
	m_dwNumNodes = 0x00;

	AL_ListSingle<AL_TreeNodeBinList<T>*> listDescendant;
	if (NULL != m_pRootNode) {
		if (TRUE == m_pRootNode->GetDescendant(listDescendant)) {
			AL_TreeNodeBinList<T>* pDescendant;
			for (DWORD dwDelete=0x00; dwDelete<listDescendant.Length(); dwDelete++) {
				if (TRUE == listDescendant.Get(dwDelete, pDescendant)) {
					if (NULL != pDescendant) {
						delete pDescendant;
						pDescendant = NULL;
					}
				}
			}
		}
	}
	delete m_pRootNode;
	m_pRootNode = NULL;
}

/**
* PreOrderTraversal
*
* @param	AL_ListSingle<T>& listOrder <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @return	BOOL
* @note Pre-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::PreOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listNode;
	if (TRUE == PreOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listWeight);
	}

	return FALSE;
}

/**
* InOrderTraversal
*
* @param	AL_ListSingle<T>& listOrder <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @return	BOOL
* @note In-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::InOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listNode;
	if (TRUE == InOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listWeight);
	}

	return FALSE;
}

/**
* PostOrderTraversal
*
* @param	AL_ListSingle<T>& listOrder <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @return	BOOL
* @note Post-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::PostOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listNode;
	if (TRUE == PostOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listWeight);
	}

	return FALSE;
}

/**
* LevelOrderTraversal
*
* @param	AL_ListSingle<T>& listOrder <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @return	BOOL
* @note Level-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::LevelOrderTraversal(AL_ListSingle<T>& listOrder, AL_ListSingle<DWORD>& listWeight) const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	if (NULL == m_pRootNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listNode;
	if (TRUE == LevelOrderTraversal(m_pRootNode, listNode)) {
		listOrder.Clear();
		return GetListDataFormListNode(listNode, listOrder, listWeight);
	}

	return FALSE;
}

/**
* GetSiblingAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<T>& listSibling <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::GetSiblingAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<T>& listSibling, AL_ListSingle<DWORD>& listWeight) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listNode;
	if (TRUE == GetSiblingAtNode(pCurTreeNode, listNode)) {
		listSibling.Clear();
		return GetListDataFormListNode(listNode, listSibling, listWeight);
	}

	return FALSE;
}

/**
* GetAncestorAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<T>& listAncestor <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::GetAncestorAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<T>& listAncestor, AL_ListSingle<DWORD>& listWeight) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listNode;
	if (TRUE == GetAncestorAtNode(pCurTreeNode, listNode)) {
		listAncestor.Clear();
		return GetListDataFormListNode(listNode, listAncestor, listWeight);
	}

	return FALSE;
}

/**
* GetDescendantAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<T>& listDescendant <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::GetDescendantAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<T>& listDescendant, AL_ListSingle<DWORD>& listWeight) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listNode;
	if (TRUE == GetDescendantAtNode(pCurTreeNode, listNode)) {
		listDescendant.Clear();
		return GetListDataFormListNode(listNode, listDescendant, listWeight);
	}

	return FALSE;
}

/**
* InsertRoot
*
* @param	const T& tData <IN> 
* @param	DWORD dwWeight <IN> 
* @return	BOOL
* @note
* @attention
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::InsertRoot(const T& tData, DWORD dwWeight)
{
	return InsertAtNode(NULL, 0x00, tData, dwWeight);
}

/**
* InsertLeftAtNode
*
* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	const T& tData <IN> 
* @param	DWORD dwWeight <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (left)
* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::InsertLeftAtNode(AL_TreeNodeBinList<T>* pCurTreeNode, const T& tData, DWORD dwWeight)
{
	return InsertAtNode(pCurTreeNode, 0x00, tData, dwWeight);
}

/**
* InsertRightAtNode
*
* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	const T& tData <IN> 
* @param	DWORD dwWeight <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (right)
* @attention  if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::InsertRightAtNode(AL_TreeNodeBinList<T>* pCurTreeNode, const T& tData, DWORD dwWeight)
{
	return InsertAtNode(pCurTreeNode, 0x01, tData, dwWeight);
}

/**
* Remove
*
* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @return	BOOL
* @note 
* @attention  the current tree node must be in the tree, remove current node and include it's descendant note
*/
template<typename T> BOOL
AL_TreeHuffmanList<T>::Remove(AL_TreeNodeBinList<T>* pCurTreeNode)
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	AL_ListSingle<AL_TreeNodeBinList<T>*> listTreeNodeDescendant;
	AL_TreeNodeBinList<T>* pTreeNodeDescendant = NULL;
	if (TRUE == pCurTreeNode->GetDescendant(listTreeNodeDescendant)) {
		//delete the descendant node
		for (DWORD dwRemoveCnt=0x00; dwRemoveCnt<listTreeNodeDescendant.Length(); dwRemoveCnt++) {
			if (TRUE == listTreeNodeDescendant.Get(dwRemoveCnt, pTreeNodeDescendant)) {
				if (NULL != pTreeNodeDescendant) {
					//delete it
					pTreeNodeDescendant->Clear();
					delete pTreeNodeDescendant;
					pTreeNodeDescendant = NULL;
				}
				else {
					//error
					return FALSE;
				}
			}
			else {
				//error
				return FALSE;
			}
		}
	}
	
	AL_TreeNodeBinList<T>* pNodeParent = pCurTreeNode->GetParent();
	if (NULL == pNodeParent && m_pRootNode != pCurTreeNode) {
		//not root node and has no parent node
		return FALSE;
	}
	if (NULL != pNodeParent) {
		//parent exist, remove the child node (pCurTreeNode)
		pNodeParent->Remove(pCurTreeNode);
	}
	
	if (m_pRootNode == pCurTreeNode) {
		//remove the root node
		m_pRootNode = NULL;
	}

	pCurTreeNode->Clear();
	delete pCurTreeNode;
	pCurTreeNode = NULL;

	m_dwNumNodes -= (listTreeNodeDescendant.Length() + 1);

	if (FALSE == RecalcDegreeHeight()) {
		return FALSE;
	}
	return TRUE;
}

/**
* GetChildNodeLeftAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @return	const AL_TreeNodeBinList<T>*
* @note get the current tree node (pCurTreeNode)'s child node at the position (left)
* @attention the current tree node must be in the tree
*/
template<typename T> const AL_TreeNodeBinList<T>* 
AL_TreeHuffmanList<T>::GetChildNodeLeftAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	return pCurTreeNode->GetChildLeft();
}

/**
* GetChildNodeRightAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @return	const AL_TreeNodeBinList<T>*
* @note get the current tree node (pCurTreeNode)'s child node at the position (right)
* @attention
*/
template<typename T> const AL_TreeNodeBinList<T>* 
AL_TreeHuffmanList<T>::GetChildNodeRightAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	return pCurTreeNode->GetChildRight();
}

/**
* IsCompleteTreeBin
*
* @param
* @return	BOOL
* @note Is Complete Binary Tree
* @attention If set binary height of h, the h layer in addition, the other layers (1 ~ h-1) has reached the maximum number of 
             nodes, right to left, the h-layer node number of consecutive missing, this is a complete binary tree .
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::IsCompleteTreeBin() const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}
	if (NULL == m_pRootNode) {
		return FALSE;
	}
	
	AL_TreeNodeBinList<T>* pTreeNode;
	AL_ListSingle<AL_TreeNodeBinList<T>*> listDescendant;
	if (FALSE == GetDescendantAtNode(m_pRootNode, listDescendant)) {
		return FALSE;
	}

	BOOL bMissing = FALSE;
	for (DWORD dwCnt=0x00; dwCnt<listDescendant->Length(); dwCnt++) {
		if (TRUE ==  listDescendant.Get(pTreeNode, dwCnt)) {
			if (NULL != pTreeNode) {
				if (m_dwHeight > pTreeNode->GetLevel()) {
					//the other layers (1 ~ h-1)
					if (NULL == pTreeNode->GetChildLeft() || NULL == pTreeNode->GetChildRight()) {
						//left or right child not exist!
						return FALSE
					}
				}
				else {
					//the h-layer
					if (TRUE == bMissing) {
						//node number of consecutive missing
						if (NULL == pTreeNode->GetChildLeft() || NULL == pTreeNode->GetChildRight()) {
							//left or right child not exist!
							return FALSE
						}
					}

					if (NULL == pTreeNode->GetChildLeft()) {
						//left child not exist!
						bMissing = TRUE;
						if (NULL != pTreeNode->GetChildRight()) {
							//right child exist!
							return FALSE;
						}
					}
					else {
						//left child exist!
						if (NULL == pTreeNode->GetChildRight()) {
							//right child not exist!
							bMissing = TRUE;
						}
					}
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

/**
* IsFullTreeBin
*
* @param
* @return	BOOL
* @note Is Full Binary Tree
* @attention A binary tree of height h is 2 ^ h-1 element is called a full binary tree.
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::IsFullTreeBin() const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	DWORD dwTwo = 2;
	DWORD dwFullTreeBinNum = 1;
	for (DWORD dwFull=0x00; dwFull<GetHeight(); dwFull++) {
		dwFullTreeBinNum *= 2;
	}
	dwFullTreeBinNum -= 1;

	return (dwFullTreeBinNum == GetNodesNum())  ? TRUE:FALSE;
}

/**
* ConvertToHuffman
*
* @param
* @return	BOOL
* @note Convert current binary tree to Huffman tree (binary tree)
		Suppose there are n weights, then construct a Huffman tree with n leaf nodes. n-weights are set to w1, w2, ..., wn, the Huffman tree structure rules:
			(1) The w1, w2, ..., wn as a forest tree with n (each tree has only one node);
			(2) in the forest root weights elect two smallest tree merge as a new tree in the left and right sub-tree, and the new root of the tree weight of its left and right sub-tree root node weights sum;
			(3) Delete selected from the forest two trees and new trees added to the forest;
			(4) Repeat (2), (3) step until only one tree in the forest until the tree is that obtained from Huffman tree.
* @attention
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::ConvertToHuffman()
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}
	if (NULL == m_pRootNode) {
		return FALSE;
	}
	
	//Get Descendant node
	//(1) The w1, w2, ..., wn as a forest tree with n (each tree has only one node);
	AL_ListSingle<AL_TreeNodeBinList<T>*> listTreeNodeDescendant;
	if (FALSE == m_pRootNode->GetDescendant(listTreeNodeDescendant)) {
		return FALSE;
	}
	
	AL_QueuePriorityList<AL_TreeNodeBinList<T>*, AL_TreeNodeBinList<T> > cQueuePriority;
	AL_TreeNodeBinList<T>* pTreeNodeDescendant = NULL;
	m_pRootNode->SetLevel(0x00);
	m_pRootNode->RemoveParent();
	m_pRootNode->RemoveLeft();
	m_pRootNode->RemoveRight();
	cQueuePriority.Push(m_pRootNode);
	for (DWORD dwDescendantCnt=0x00; dwDescendantCnt<listTreeNodeDescendant.Length(); dwDescendantCnt++) {
		if (TRUE == listTreeNodeDescendant.Get(dwDescendantCnt, pTreeNodeDescendant)) {
			if (NULL != pTreeNodeDescendant) {
				pTreeNodeDescendant->SetLevel(0x00);
				pTreeNodeDescendant->RemoveParent();
				pTreeNodeDescendant->RemoveLeft();
				pTreeNodeDescendant->RemoveRight();
				cQueuePriority.Push(pTreeNodeDescendant);
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	//Rebuilt Huffman Tree
	m_dwDegree = 0x00;
	m_dwHeight = TREEHUFFMANLIST_HEIGHTINVALID;
	m_pRootNode = NULL;
	AL_TreeNodeBinList<T>* pTreeNodeSmallest = NULL;
	AL_TreeNodeBinList<T>* pTreeNodeSmaller = NULL;
	AL_TreeNodeBinList<T>* pTreeNode = NULL;

	while (0x01 < cQueuePriority.Size()) {
		//loop all, until only one tree in the priority queue 
		//(2) in the forest root weights elect two smallest tree merge as a new tree in the left and right sub-tree, and the new root of the tree weight of its left and right sub-tree root node weights sum;
		if (TRUE == cQueuePriority.Pop(pTreeNodeSmallest) && TRUE == cQueuePriority.Pop(pTreeNodeSmaller)){
			if (NULL != pTreeNodeSmallest && NULL != pTreeNodeSmaller) {
				//rebuilt the root node
				pTreeNode = new AL_TreeNodeBinList<T>;
				if (NULL == pTreeNode) {
					return FALSE;
				}
				pTreeNode->SetLevel(0x00);
				pTreeNode->SetWeight(pTreeNodeSmallest->GetWeight() + pTreeNodeSmaller->GetWeight());
				m_pRootNode = pTreeNode;

				if (TRUE == m_pRootNode->InsertLeft(pTreeNodeSmallest) 
					&& TRUE == m_pRootNode->InsertRight(pTreeNodeSmaller)) {
						//(3) Delete selected from the forest two trees and new trees added to the forest;
						m_dwNumNodes++;
						cQueuePriority.Push(m_pRootNode);
				}
				else {
					return FALSE;
				}
			}
			else {
				return FALSE;
			}
		}
		else{
			return FALSE;
		}
		//(4) Repeat (2), (3) step until only one tree in the forest until the tree is that obtained from Huffman tree.
	}
	
	if (FALSE == RecalcDegreeHeight()) {
		return FALSE;
	}
	return TRUE;
}

/**
* InsertAtNode
*
* @param	AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	DWORD dwIndex <IN>
* @param	const T& tData <IN> 
* @param	DWORD dwWeight <IN> 
* @return	BOOL
* @note insert the tData as child tree node to the current tree node (pCurTreeNode) at the position (dwIndex)
* @attention if NULL == pCurTreeNode, it will be insert as root tree node, the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::InsertAtNode(AL_TreeNodeBinList<T>* pCurTreeNode, DWORD dwIndex, const T& tData, DWORD dwWeight)
{
	AL_TreeNodeBinList<T>* pTreeNode = NULL;
	if (TRUE == IsEmpty()) {
		if (NULL != pCurTreeNode) {
			//error can not insert to the current node pCurTreeNode, is not exist in the tree
			return FALSE;
		}
		else {
			pTreeNode = new AL_TreeNodeBinList<T>;
			if (NULL ==  pTreeNode) {
				return FALSE;
			}
			pTreeNode->SetData(tData);
			pTreeNode->SetLevel(0x00);
			pTreeNode->SetWeight(dwWeight);

			m_pRootNode = pTreeNode;
			m_dwDegree = 0x00;
			m_dwHeight = 0x00;			//empty tree 0xffffffff (-1)
			m_dwNumNodes++;
			return TRUE;
		}
	}

	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	//inset to the current tree node
	pTreeNode = new AL_TreeNodeBinList<T>;
	if (NULL ==  pTreeNode) {
		return FALSE;
	}
	pTreeNode->SetData(tData);
	pTreeNode->SetLevel(pCurTreeNode->GetLevel() + 1);
	pTreeNode->SetWeight(dwWeight);

	if (FALSE ==  pCurTreeNode->Insert(dwIndex, pTreeNode)) {
		delete pTreeNode;
		pTreeNode = NULL;
		return FALSE;
	}

	DWORD dwCurNodeDegree = 0x00;
	//loop all node to get the current node degree
	if (m_dwDegree < pCurTreeNode->GetDegree()) {
		m_dwDegree = pCurTreeNode->GetDegree();
	}

	if (m_dwHeight < pTreeNode->GetLevel()) {
		m_dwHeight =pTreeNode->GetLevel();
	}
	m_dwNumNodes++;

	return TRUE;
}


/**
* PreOrderTraversal
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
* @return	BOOL
* @note Pre-order traversal
* @attention
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::PreOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listOrder.Clear();

	//Recursion Traversal
	return PreOrderTraversalRecursion(pCurTreeNode, listOrder);

	//Not Recursion Traversal
	AL_StackList<AL_TreeNodeBinList<T>*> cStack;
	AL_TreeNodeBinList<T>* pTreeNode = const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode);

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			listOrder.InsertEnd(pTreeNode);
			if (NULL != pTreeNode->GetChildRight()) {
				//push the child right to stack
				cStack.Push(pTreeNode->GetChildRight());
			}
			pTreeNode = pTreeNode->GetChildLeft();
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL == pTreeNode) {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}

	}
	return TRUE;
}

/**
* InOrderTraversal
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
* @return	BOOL
* @note In-order traversal
* @attention
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::InOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listOrder.Clear();
	//Recursion Traversal
	return InOrderTraversalRecursion(pCurTreeNode, listOrder);

	//Not Recursion Traversal
	AL_StackList<AL_TreeNodeBinList<T>*> cStack;
	AL_TreeNodeBinList<T>* pTreeNode = const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode);

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			cStack.Push(pTreeNode);
			pTreeNode = pTreeNode->GetChildLeft();
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL !=  pTreeNode) {
				listOrder.InsertEnd(pTreeNode);
				if (NULL != pTreeNode->GetChildRight()){
					//child right exist, push the node, and loop it's left child to push
					pTreeNode = pTreeNode->GetChildRight();
				}
				else {
					//to pop the node in the stack
					pTreeNode = NULL;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

/**
* PostOrderTraversal
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
* @return	BOOL
* @note Post-order traversal
* @attention
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::PostOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listOrder.Clear();

	//Recursion Traversal
	return PostOrderTraversalRecursion(pCurTreeNode, listOrder);

	//Not Recursion Traversal
	AL_StackList<AL_TreeNodeBinList<T>*> cStack;
	AL_TreeNodeBinList<T>* pTreeNode = const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode);
	AL_StackList<AL_TreeNodeBinList<T>*> cStackReturn;
	AL_TreeNodeBinList<T>* pTreeNodeReturn = NULL;

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			cStack.Push(pTreeNode);
			if (NULL != pTreeNode->GetChildLeft()) {
				pTreeNode = pTreeNode->GetChildLeft();
			}
			else {
				//has not left child, get the right child
				pTreeNode = pTreeNode->GetChildRight();
			}
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL !=  pTreeNode) {
				listOrder.InsertEnd(pTreeNode);
				if (NULL != pTreeNode->GetChildLeft() && NULL != pTreeNode->GetChildRight()){
					//child right exist
					cStackReturn.Top(pTreeNodeReturn);
					if (pTreeNodeReturn != pTreeNode) {
						listOrder.RemoveAt(listOrder.Length()-1);
						cStack.Push(pTreeNode);
						cStackReturn.Push(pTreeNode);
						pTreeNode = pTreeNode->GetChildRight();
					}
					else {
						//to pop the node in the stack
						cStackReturn.Pop(pTreeNodeReturn);
						pTreeNode = NULL;
					}
				}
				else {
					//to pop the node in the stack
					pTreeNode = NULL;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

/**
* LevelOrderTraversal
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
* @return	BOOL
* @note Level-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::LevelOrderTraversal(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}
	listOrder.Clear();

	/*
	AL_ListSingle<AL_TreeNodeBinList<T>*> listNodeOrder;
	listNodeOrder.InsertEnd(const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode));
	//loop the all node
	DWORD dwNodeOrderLoop = 0x00;
	AL_TreeNodeBinList<T>* pNodeOrderLoop = NULL;
	AL_TreeNodeBinList<T>* pNodeOrderChild = NULL;
	while (TRUE == listNodeOrder.Get(pNodeOrderLoop, dwNodeOrderLoop)) {
		dwNodeOrderLoop++;
		if (NULL != pNodeOrderLoop) {
			listOrder.InsertEnd(pNodeOrderLoop);
			pNodeOrderChild = pNodeOrderLoop->GetChildLeft();
			if (NULL != pNodeOrderChild) {
				queueOrder.Push(pNodeOrderChild);
			}
			pNodeOrderChild = pNodeOrderLoop->GetChildRight();
			if (NULL != pNodeOrderChild) {
				queueOrder.Push(pNodeOrderChild);
			}
		}
		else {
			//error
			return FALSE;
		}
	}
	return TRUE;
	*/
	
	AL_QueueList<AL_TreeNodeBinList<T>*> queueOrder;
	queueOrder.Push(const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode));
	
	AL_TreeNodeBinList<T>* pNodeOrderLoop = NULL;
	AL_TreeNodeBinList<T>* pNodeOrderChild = NULL;
	while (FALSE == queueOrder.IsEmpty()) {
		if (TRUE == queueOrder.Pop(pNodeOrderLoop)) {
			if (NULL != pNodeOrderLoop) {
				listOrder.InsertEnd(pNodeOrderLoop); 
				pNodeOrderChild = pNodeOrderLoop->GetChildLeft();
				if (NULL != pNodeOrderChild) {
					queueOrder.Push(pNodeOrderChild);
				}
				pNodeOrderChild = pNodeOrderLoop->GetChildRight();
				if (NULL != pNodeOrderChild) {
					queueOrder.Push(pNodeOrderChild);
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}
	return TRUE;
}

/**
* PreOrderTraversalRecursion
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
* @return	BOOL
* @note Pre-order traversal
* @attention Recursion Traversal
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::PreOrderTraversalRecursion(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	//Do Something with node
	if (FALSE == listOrder.InsertEnd(const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode))) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildLeft()) {
		if (FALSE == PreOrderTraversalRecursion(pCurTreeNode->GetChildLeft(), listOrder)) {
			return FALSE;
		}
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		if (FALSE == PreOrderTraversalRecursion(pCurTreeNode->GetChildRight(), listOrder)) {
			return FALSE;
		}
	}

	//Recursion End
	return TRUE;
}

/**
* InOrderTraversalRecursion
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
* @return	BOOL
* @note In-order traversal
* @attention Recursion Traversal
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::InOrderTraversalRecursion(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildLeft()) {
		if (FALSE == InOrderTraversalRecursion(pCurTreeNode->GetChildLeft(), listOrder)) {
			return FALSE;
		}
	}

	//Do Something with node
	if (FALSE == listOrder.InsertEnd(const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode))) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		if (FALSE == InOrderTraversalRecursion(pCurTreeNode->GetChildRight(), listOrder)) {
			return FALSE;
		}
	}

	//Recursion End
	return TRUE;
}

/**
* PostOrderTraversalRecursion
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder <OUT>
* @return	BOOL
* @note Post-order traversal
* @attention Recursion Traversal
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::PostOrderTraversalRecursion(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	if(NULL != pCurTreeNode->GetChildLeft()) {
		if (FALSE == PostOrderTraversalRecursion(pCurTreeNode->GetChildLeft(), listOrder)) {
			return FALSE;
		}
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		if (FALSE == PostOrderTraversalRecursion(pCurTreeNode->GetChildRight(), listOrder)) {
			return FALSE;
		}
	}

	//Do Something with node
	if (FALSE == listOrder.InsertEnd(const_cast<AL_TreeNodeBinList<T>*>(pCurTreeNode))) {
		return FALSE;
	}

	//Recursion End
	return TRUE;
}

/**
* GetSiblingAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling <OUT>
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::GetSiblingAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listSibling.Clear();
	return pCurTreeNode->GetSibling(listSibling);
}

/**
* GetAncestorAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::GetAncestorAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listAncestor.Clear();
	return pCurTreeNode->GetAncestor(listAncestor);
}

/**
* GetDescendantAtNode
*
* @param	const AL_TreeNodeBinList<T>* pCurTreeNode <IN> 
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention the current tree node must be in the tree
*/
template<typename T> BOOL 
AL_TreeHuffmanList<T>::GetDescendantAtNode(const AL_TreeNodeBinList<T>* pCurTreeNode, AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant) const
{
	if (NULL == pCurTreeNode) {
		return FALSE;
	}

	listDescendant.Clear();
	return pCurTreeNode->GetDescendant(listDescendant);
}

/**
* RecalcDegreeHeight
*
* @param	
* @return	BOOL
* @note recalculate Degree Height
* @attention 
*/
template<typename T> BOOL
AL_TreeHuffmanList<T>::RecalcDegreeHeight()
{
	if (NULL == m_pRootNode) {
		if (TRUE == IsEmpty()) {
			m_dwDegree = 0x00;
			m_dwHeight = TREEHUFFMANLIST_HEIGHTINVALID;
			return TRUE;
		}
		else {
			return FALSE;
		}
	}
	m_dwDegree = m_pRootNode->GetDegree();
	m_dwHeight = m_pRootNode->GetLevel();

	//loop all the node
	AL_ListSingle<AL_TreeNodeBinList<T>*> listTreeNodeDescendant;
	if (TRUE == m_pRootNode->GetDescendant(listTreeNodeDescendant)) {
		DWORD dwNumNodes = listTreeNodeDescendant.Length() + 1;
		if (m_dwNumNodes != dwNumNodes) {
			return FALSE;
		}

		AL_TreeNodeBinList<T>* pTreeNodeDescendant = NULL;
		for (DWORD dwLoopCnt=0x00; dwLoopCnt<listTreeNodeDescendant.Length(); dwLoopCnt++) {
			if (TRUE == listTreeNodeDescendant.Get(dwLoopCnt, pTreeNodeDescendant)) {
				if (NULL != pTreeNodeDescendant) {
					if (m_dwDegree < pTreeNodeDescendant->GetDegree()) {
						m_dwDegree = pTreeNodeDescendant->GetDegree();
					}
					if (m_dwHeight < pTreeNodeDescendant->GetLevel()) {
						m_dwHeight = pTreeNodeDescendant->GetLevel();
					}
				}
				else {
					//error
					return FALSE;
				}
			}
			else {
				//error
				return FALSE;
			}
		}
	}
	return TRUE;
}

/**
* GetListDataFormListNode
*
* @param	
* @param	const AL_ListSingle<AL_TreeNodeBinList<T>*>& listNode <IN>
* @param	AL_ListSingle<T>& listData <OUT>
* @param	AL_ListSingle<DWORD>& listWeight <OUT> (default value: AL_ListSingle<DWORD>())
* @note
* @attention 
*/
template<typename T> BOOL
AL_TreeHuffmanList<T>::GetListDataFormListNode(const AL_ListSingle<AL_TreeNodeBinList<T>*>& listNode, AL_ListSingle<T>& listData, AL_ListSingle<DWORD>& listWeight) const
{
	AL_TreeNodeBinList<T>* pNodeLoop = NULL;
	listData.Clear();
	listWeight.Clear();
	//loop all node in list
	for (DWORD dwLoopCnt=0x00; dwLoopCnt<listNode.Length(); dwLoopCnt++) {
		if (TRUE == listNode.Get(dwLoopCnt, pNodeLoop)) {
			if (NULL != pNodeLoop) {
				if (FALSE == listData.InsertEnd(pNodeLoop->GetData())
					|| FALSE == listWeight.InsertEnd(pNodeLoop->GetWeight())) {
					return FALSE;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}
	return TRUE;
}
#endif // CXX_AL_TREEHUFFMANLIST_H
/* EOF */